package 归并排序;

import java.util.Arrays;

public class mergesort {

    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length-1);
    }

    public static void mergeSortInternal(int[] array,int low,int high){
        if(low >=high){
            return;
        }
        int mid=(low+high)/2;
        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid+1,high);
        merge(array,low,mid,high);
    }

    public static void merge(int[] array,int low,int mid,int high){
        int s1=low;
        int e1=mid;
        int s2=mid+1;
        int e2=high;
        int[] tmp=new int[high-low+1];
        int k=0;

        while(s1 <= e1 && s2 <= e2){
            if(array[s1]< array[s2]){
                tmp[k]=array[s1];
                k++;
                s1++;
            }else{
                tmp[k]=array[s2];
                k++;
                s2++;
            }
        }
        while(s1 <= e1){
            tmp[k]=array[s1];
            k++;
            s1++;
        }
        while(s2 <= e2){
            tmp[k]=array[s2];
            k++;
            s2++;
        }
        //拷贝tmp数组元素放到原来的数组array中
        for(int i=0;i<k;i++){
            array[i+low]=tmp[i];
        }

    }

    public static void main(String[] args) {
        int[] array={12,5,9,34,0,33,6,55};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
